#include <vector>
class Solution {
public:
    // bfs 
    // vector<vector<int>> levelOrder(TreeNode* root) {
    //     vector<vector<int>> ans;
    //     if(root == NULL) return ans;
    //     TreeNode * node;
    //     queue<TreeNode *> q;
    //     q.push(root);
    //     while(!q.empty()){
    //         int cnt = q.size();
    //         vector<int> tmp;  
    //         for(int i = 0; i < cnt; i++){
    //             node =  q.front();
    //             tmp.emplace_back(node->val);
    //             if(node->left) q.push(node->left);
    //             if(node->right) q.push(node->right);
    //             q.pop();
    //         }
    //         ans.emplace_back(tmp);
    //     }
    //     return ans;
    // }

    void dfs(TreeNode* root, int k, vector<vector<int>> &ans){
        if(root == NULL) return;
        if(k == ans.size()) ans.emplace_back(vector<int>());
        ans[k].emplace_back(root->val);
        dfs(root->left, k + 1, ans);
        dfs(root->right, k + 1, ans);
        return;
    }
    //dfs
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        dfs(root, 0, ans);
        return ans;
    }
};